/*
 * matrix_graph.c
 *
 *  Created on: 2020��1��9��
 *      Author: Administrator
 */
#include <stdbool.h>
#ifndef MATRIX_GRAPH_C_
#define MATRIX_GRAPH_C_

#define MaxVertexNum 20
#define INFINITY 32768

typedef int Vertex;
typedef int WeightType;

bool visited[MaxVertexNum]; // 记录节点是否被访问 ，全局变量

typedef struct GNode {
	WeightType graph[MaxVertexNum][MaxVertexNum];  // �ڽӾ���
	int vertex_number;   // 顶点数量
	int edge_number;     // 边数量
	bool is_directed;    // 是否为有向图
} GNode, *AdjMatrix;

typedef struct ENode {
	Vertex v1, v2;
	WeightType weight;
}ENode, *Edge;

AdjMatrix init_graph(int vertex_number);

void build_graph(AdjMatrix graph, Edge edges[], int edges_number);

Edge* build_edges(int edges_number, int input[][3]);

bool insert_edge(AdjMatrix graph, Edge edge);

bool has_edge(AdjMatrix graph, Vertex v1, Vertex v2);

void visit(Vertex v);

bool is_visited(Vertex v);

bool is_not_visited(Vertex v);
/**
 * 获取与起点邻接的第一个结点
 * 返回值：如果存在，返回结点；不存在，返回-1
 */
Vertex first_adj_vertex(AdjMatrix graph, Vertex start);
/**
 * 获取与起点邻接的最后一个结点
 * 返回值：如果存在，返回结点；不存在，返回-1
 */
Vertex last_adj_vertex(AdjMatrix graph, Vertex start);
/**
 * 获取与起点邻接的第一个结点的下一个结点
 * 返回值：如果存在，返回结点；不存在，返回-1
 */
Vertex next_adj_vertex(AdjMatrix graph, Vertex start, Vertex next);
/**
 * 获取与起点邻接的第一个结点的前一个结点
 * 返回值：如果存在，返回结点；不存在，返回-1
 */
Vertex pre_adj_vertex(AdjMatrix graph, Vertex start, Vertex next);
/**
 * 清空全局变量visited
 */
void clear_visited(int vertex_number);
/**
 * 深度优先遍历（递归）
 */
void dfs(AdjMatrix graph, Vertex start);
/**
 * 深度优先遍历（非递归）
 */
void unr_dfs(AdjMatrix graph, Vertex start);
/**
 * 广度优先遍历
 */
void bfs(AdjMatrix graph, Vertex start);

void print_matrix_graph(AdjMatrix graph);

#endif /* MATRIX_GRAPH_C_ */
